#include <iostream>
#include <list>
#include <unordered_map>
#include <string>


class LFUCache {
public:


    LFUCache(int capacity) : _capacity(capacity), minFreq(0) {}

    int get(std::string key) {
        if (_capacity == 0 || key_table.find(key) == key_table.end()){
            return -1;
        }
        auto it = key_table[key];
        int val = it->value;
        put(key, val); // 更新频率和位置
        return val;
    }

    void put(std::string key, int value) {
        if (_capacity == 0) return;
        if (key_table.find(key) != key_table.end()) {
            for_old_key(key, value);
        } else {
            for_new_key(key, value);
        }
    }




private:
    struct CacheNode {
        std::string key;
        int value;
        int freq;
        CacheNode(std::string k, int v, int f) : key(k), value(v), freq(f) {}
    };

    int _capacity;
    int minFreq; // 当前最小频率
    std::unordered_map<std::string, std::list<CacheNode>::iterator> key_table; // 键到其频率列表中的位置映射
    std::unordered_map<int, std::list<CacheNode>> freq_table; // 频率到键值对列表的映射

    void for_old_key(std::string &key, int value) {
        auto it = key_table[key];
        freq_table[it->freq].erase(it);
        if (freq_table[it->freq].empty()) {
            freq_table.erase(it->freq);
            if (minFreq == it->freq) ++minFreq;
        }
        int newFreq = ++(it->freq);
        freq_table[newFreq].push_front(CacheNode(key, value, newFreq));
        key_table[key] = freq_table[newFreq].begin();
    }

    void for_new_key(std::string &key, int value) {
        if (key_table.size() == _capacity) {
            std::string delKey = freq_table[minFreq].back().key;
            freq_table[minFreq].pop_back();
            if (freq_table[minFreq].empty()) freq_table.erase(minFreq);
            key_table.erase(delKey);
        }
        minFreq = 1;
        freq_table[1].push_front(CacheNode(key, value, 1));
        key_table[key] = freq_table[1].begin();
    }
};

int main() {
    LFUCache cache(2);

    cache.put("one", 1);
    cache.put("two", 2);
    std::cout << cache.get("one") << std::endl; // 返回 1
    cache.put("three", 3); // 淘汰 "two"
    std::cout << cache.get("two") << std::endl; // 返回 -1 (未找到)
    std::cout << cache.get("three") << std::endl; // 返回 3
    cache.put("four", 4); // 淘汰 "one"
    std::cout << cache.get("one") << std::endl; // 返回 -1 (未找到)
    std::cout << cache.get("three") << std::endl; // 返回 3
    std::cout << cache.get("four") <<std:: endl; // 返回 4

    return 0;
}